The invention relates generally to error correction code decoding mechanisms and more particularly to the decoding of Bose-Chaudhuri-Hocquenghem (BCH) correction codes, including Reed-Solomon error correction codes.
The use of increasingly higher density storage media in digital computer systems has caused an increase in the potential for defect-related data errors. To reduce data loss as a result of such data corruption, error correction codes are employed to correct the erroneous data.
Prior to storing data on a storage device, such as a magnetic disk or tape, it is encoded to form redundancy symbols. The redundancy symbols are appended to the data symbols to form code words, which are then stored on the storage device. When the stored data is retrieved from the storage device for decoding, the redundancy symbols provide information which allows the decoder to recognize errors and, if possible, reconstruct the original code word. A detailed description of decoding may be found in xe2x80x9cError-Correcting Codes,xe2x80x9d Second Edition, by W. Wesley Peterson and E. J. Weldon, Jr. (MIT Press, 1972), incorporated herein by reference.
One widely-used error correction code is the Reed-Solomon code. Error detection and correction techniques for Reed-Solomon codes are well known.
To correct errors, a decoder must determine the locations and values (or magnitudes) of the detected errors. The decoder first computes error syndromes, which it then uses to generate an error locator polynomial. Once the error locator polynomial has been generated, each error location and value may be determined.
Error locations are determined by solving for the roots of the error locator polynomial "sgr"(x) of degree t or less, where t is the number of errors that can be corrected. The solution or roots of the equation "sgr"(x)=0 correspond to the locations of the errors. These roots are of the form x=xcex1i, where xcex1 is the primitive element of the Galois Field GF(pq) used to encode the data. Once all t roots have been found, the corresponding error values are calculated using the well-known Forney algorithm. The data can then be corrected to produce an error-free data symbol.
Typically, when a codeword is read from the storage media, error correction is performed, as the corrected data is to be provided to a user. There are, however, some instances in which it is useful to determine the number of errors that have occurred in a codeword, but decoding is unnecessary. For example, in a disk test application, codewords are written to and read from a new disk and the number of errors compared to a threshold in order to assess the quality of a new disk. In yet another example, in read-after-write operations of a tape drive, which is typically less reliable than disk, it is desirable to determine the error count immediately after the completion of the read-after-write operation is completed so that the read codeword can be relocated to another storage location on that tape drive if the error count is too high.
There are several prior approaches to determining the number of errors in a codeword retrieved from storage. One approach is to use a conventional decoding algorithm to find the error locator polynomial, the degree of which corresponds to the number of errors. This approach is quite complex, as it requires the full implementation of either of the well-known Berlekamp-Massey or Euclidean algorithms, which are described in xe2x80x9cTheory and Practice of Error Control Codesxe2x80x9d by Richard E. Blahut (Addison-Wesley, 1983), incorporated herein by reference.
Another prior technique uses a theorem, or more specifically, Theorem 9.9 on page 284 of the above-referenced text by Peterson and Weldon. This theorem states that a vxc3x97v matrix M with syndromes as elements is singular (i.e., the determinant is zero) if there are fewer than v errors per code block, and the matrix is nonsingular (i.e., the determinant is nonzero) if there are exactly v errors per code block.
In one aspect of the invention, determining a number of errors in an error correction codeword includes determining from the error correction codeword a syndrome polynomial which is associated with an error locator polynomial of a degree and having error locator polynomial coefficients, operating on the syndrome polynomial to determine the degree without determining the error locator polynomial coefficients, and identifying the degree as the number of errors in the error correction codeword.
Embodiments of the invention may include one or more of the following features.
It is determined whether or not the number of errors exceeds an error threshold. If the codeword is stored in a storage location on a storage device and if it is determined that the number of errors exceeds an error threshold, the error correction code is rewritten to the storage location, or a different storage location, on the storage device.
In one embodiment, the syndrome polynomial operation includes a Euclidean process that determines the degree without determining the coefficients. For a t error correcting code, the performance of the Euclidean process includes initializing a divisor value as corresponding to the computed syndrome polynomial and a dividend value which corresponds to a polynomial x2t. The Euclidean process includes the following: initializing a degree count to zero and a degree count indicator value to zero; producing a quotient value from a leading term of the dividend value and a leading term of the divisor value; generating a remainder value from the quotient value; updating the dividend for the remainder value; incrementing the degree count by one and setting the degree count indicator value to one if the degree count indicator value is set to zero. The steps of producing, generating, incrementing and setting are repeated until the difference of the degree of the divisor value subtracted from the dividend value is less than zero. The process further includes: setting the degree count indicator value to zero; interchanging the divisor value and remainder value; and determining if the degree of the remainder value is less than t. If the degree of the remainder value is less that t, then the process indicates that the degree count is the number of errors. If the degree of the remainder value is not less than. t, then the process repeats the steps of producing, generating, incrementing, setting, repeating, interchanging and determining.
In another embodiment, the syndrome polynomial includes syndrome values and the operation on the syndrome polynomial includes arranging the computed syndrome values to form a matrix having rows of unequal lengths and examining at least one row for nonzero values. The syndrome polynomial operation further includes performing row operations on the rows of the matrix. For a matrix which includes t rows, the syndrome polynomial operation includes indicating that there are fewer than t errors in the codeword if an examined last row txe2x88x921 has no nonzero values. Alternately, the step of examining is performed prior to each of the row operations. The steps of examining and performing are repeated until an examined row is equal to all zero values to indicate a number of errors corresponding to the number of the row or the row is row t to indicate that the number of errors is at least t.
In another aspect of the invention, the error number determination is used to test storage devices. Testing the storage device includes reading codewords from the storage device, generating syndrome values for the codewords, determining from the syndrome values for each of the codewords a degree of an error locator polynomial without computing the coefficients of the error locator polynomial, the degree corresponding to a number of errors. The number of errors is then compared to an error threshold. The storage device is rejected if the number of errors of a predetermined number of one or more of the read codewords exceeds threshold.
Among the advantages of the present invention are the following. The error count can be determined without computing the error locator polynomial. Therefore, the error count for a codeword is realized with a much smaller number of operations than are required by either of the Berlekamp-Massey or Euclidean algorithms. This is quite useful for applications that need to quickly establish the condition of the codeword. Because only the degree is determined, a Euclidean approach is advantageously modified to eliminate error locator polynomial computation steps, e.g., coefficient multiplications and error locator polynomial updates, which consume memory and computation cycles. Only the degree of the error locator polynomial need be updated and retained. The actual error locator polynomial, which can be obtained from all of the quotient values, need not ever be computed, and the quotient values may be discarded once the degrees of the quotients are used to update the degree of the error locator polynomial.
Additionally, the Euclidean computation polynomials have the property that degree of the remainder value (remainder polynomial) is less than the degree of the divisor value (divisor polynomial), the degree of each quotient value is at least one and, consequently, the degree of the error locator polynomial is always increasing during the iterative Euclidean process. Therefore, if after t iterations the degree of the error locator polynomial is at least t and the degree of the remainder polynomial is still not lower than t, there is no need to proceed further, since the error locator polynomial degree will exceed t for any additional computations.
The matrix evaluation makes the above-mentioned textbook theorem readily applicable to error counting by providing a condition for the case of more than v errors. The evaluation need not examine matrices of different sizes to provide an accurate error count.
Other features and advantages of the invention will be apparent from the following detailed description and from the claims.